Achieving optimal performance, such as short response time, high throughput, user fairness, and so on, is often a central goal in designing computerized systems, including communication systems, Internet web servers, supercomputers, and computer networks. Although it can be easy to come up with many possible configurations for a computerized system, it is usually a difficult and time-consuming task to select the best possible, or most optimal, configuration among many such possibilities so that system performance is optimized.
For example, designing a high-performance Internet web server system involves determining the best possible combination of hardware components, scheduling or dispatching policies, and configuration parameter values, such as cache sizes and timeout values, for each server and database. Since there is a large number of possible configurations, and since estimating the performance of each configuration via simulation or experiment often requires tens of minutes, it is impractical to accurately evaluate the performance of all possible configurations to identify the most optimal configuration.
One prior art approach for finding the optimal solution, or configuration, from a large set of possible solutions is known as local search. Local search iteratively finds a better solution from the “neighbors” of a current solution, and replaces the current solution with a neighboring, better solution. A local search algorithm may be augmented with existing mechanisms to escape from a locally optimal but globally sub-optimal solution.
Although local search was originally developed for non-stochastic optimization problems, it has recently started to receive attention as a promising approach for optimizing stochastic systems whose performance can be estimated via simulations or experiments, where the terminology simulation is used synonymously with the terminology experiment herein. For example, one prior art local search approach applies a recursive random search algorithm to the performance optimization of network protocols, where the performance is estimated via simulations. Another prior art approach applies a hill-climbing algorithm to optimize the configuration parameters of Internet web servers, where the performance is measured via experiments.
Although local search limits the search space to a smaller number of system configurations, simulations or experiments often require many iterations, such as many samples of simulated performance, simply to estimate the performance of a single configuration. For example, a test run may require fifteen minutes to estimate the mean response time for each configuration of an Internet web server. As a result, just a small number out of many possible configuration parameters may be effectively optimized via local search. Therefore, to optimize the performance of stochastic systems via local system, it is important to minimize the time needed for simulations to find a better system configuration from neighboring system configurations.
For these and other reasons, there is a need for the present invention.